/**
 * 
 */
package problem;


import datastructure.Queue;
import datastructure.impl.SeqQueue;

/**
 * 农夫过河问题：一个农夫带了一只狼，一只羊和一棵白菜，身处河的南岸。他要把这些东西
 * 全部运到北岸。农夫只有一只船，一次只能带一件物品。
 * 约束：狼和羊的没有农夫的情况下不能在一起，羊和白菜在没有农夫的情况下不能在一起。
 * @author Jun
 *
 */
public class farmerProblem {

	/**
	 * problem status: [人狼白菜羊]0000 -> 1111
	 * Constraint: 011*，100*，0*11,1*00
	 * Array[16]: point to the previous index. 这些构成了一条路径
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		farmerProblem ins = new farmerProblem();
		ins.solve();
		// 输出是逆路径
		// 15 6 14 2 11 9 0
		
	}
	
	public void solve(){
		
		Queue<Integer> result = new SeqQueue<Integer>(Integer.class);
		
		//Initialization
		int[] arr = new int[16];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = -1;	//unvisit
		}
		
		arr[0] = 0;
		int start = 0;
		int status = 0;
		result.enQueue(start);
		
		while(!result.isEmptyQueue()&&arr[15]==-1){
			
			status = result.frontQueue();
			result.DeQueue();
			// i表示移动的物体
			for(int i=1 ; i<=8; i<<=1){
	
				//检查状态，移动物品与农夫是否在同一岸
				if(((i&status)!=0)^((0x8&status)!=0))
					continue;
				
				start = status^(i|0x8);
				
				if(arr[start]==-1&&Constraint(status)){
					
					arr[start] = status;
//					if(start == 15) break;					
					result.enQueue(start);
					
				}
				//如果状态可以迁移
					//判断迁移的状态是否满足约束
				
				//迁移状态满足约束
					//将新状态加入队列
					//赋值arr[新状态]= previous index
						//新状态是否等于目标状态
								//break;
					//将i重置为1

			}
			
		}
		
		//print
		if(arr[15]!=-1){
			
			System.out.println("The reverse path!");
			for(int loc = 15; loc>=0;loc= arr[loc]){
				
				System.out.printf("The location is %d \n",loc);
				if(loc ==0) break;
			}
			
		}
		else {
			System.out.println("No Solution\n");
		}
		
		
	}
	
	public boolean Constraint(int status){
		
		int f = farmerLoc(status);
		int b = BabageLoc(status);
		int s = sheepLoc(status);
		int w = wolfLoc(status);
		
		if((b==s)&&f!=b) return false;
		if((w==s)&&f!=w) return false;
		
		return true;
		
	}

	public int farmerLoc(int status){		
		return  (status&0x8)>>3;
	}
	
	public int wolfLoc(int status){		
		return  (status&0x4)>>2;
	}
	
	public int BabageLoc(int status){		
		return (status&0x2)>>1;
	}
	
	public int sheepLoc(int status){		
		return (status&0x1);
	}
	
	
	
	
	
	
	
	
}
